package algorithm;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author maguangqi
 * @version 1.0
 * https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
 * 111题,计算树的最小深度
 * @date 2020/7/7 21:54
 */
public class MinDepth111 {
    /**
     * 解法一: BFS
     * 最小深度是某一个节点是叶子节点,也就是它没有左子树和右子树
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int minDepth = 0;
        while (!queue.isEmpty()) {
            minDepth++;
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                //如果当前节点即没有左子树,也没有右子树,说明它是个叶子节点,那么它肯定时最短深度
                if (curNode.left == null && curNode.right == null) {
                    return minDepth;
                }
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
        }
        return minDepth;
    }

    /**
     *使用DFS
     *计算最小深度
     * 我们可以使用最大深度的计算,即求左子树和右子树的最小值,看似正确,其实不对,因为如果某一个节点没有
     * 左子树或者右子树的时候,此时最小深度是0.不满足题目条件,因此我们应该考虑如果左子树为空的时候,就应该计算
     * 右子树的最小深度.
     */

    public int minDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //先计算左子树的最小深度
        int left = minDepth2(root.left);
        //再计算右子树的最小深度
        int right = minDepth2(root.right);
        //如果left和right都等于0,说明只有一个根节点,返回1
        //如果left和right有一个为空,说明他们只有一个子节点,只需要返回他们的最小深度+1
        //如果left和right都不为空,返回他们2个的最小值+1
        return (left == 0 || right == 0) ? (left + right + 1) : Math.min(left, right) + 1;
    }
}
